package 第五周;

/*
 * @author  YxinMiracle
 * @date  2022-05-01 18:05
 * @Gitee: https://gitee.com/yxinmiracle
 */

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class 分割数组的最大值 {

    public int splitArray(int[] nums, int m) {
        List<Integer> list = new ArrayList<>();
        for (Integer item : nums) {
            list.add(item);
        }
        List<Integer> collect = list.stream().sorted().collect(Collectors.toList()); // 从小到大
        int sum = list.stream().mapToInt(x -> x).sum();
        // 使用二分法进行解题
        int left = collect.get(collect.size() - 1);
        int right = sum;
        while (left < right) {
            int min = (left + right) >> 1;
            if (validate(nums, m, min)) {
                right = min;
            } else {
                left = min + 1;
            }
        }
        return right;

    }

    /**
     * 校验是否满足条件
     *
     * @param nums   数据源
     * @param m      m个box可以分成吗
     * @param target 最大值为target
     * @return 是否成功
     */
    public boolean validate(int[] nums, int m, int target) {
        int box = 0; // box中累计的数值
        int count = 1; // 有几个box
        for (int i = 0; i < nums.length; i++) {
            if (box + nums[i] <= target) {
                box += nums[i];
            } else {
                // 已经超过了
                count++;
                box = nums[i];
            }
        }
        return count == m;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{-1, 3, -2, 49, 2};
        new 分割数组的最大值().splitArray(nums, 2);
    }

}
